package leetCode.firstWeek;

import java.lang.reflect.Array;
import java.util.*;

public class Code_15 {

  public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> ls = new ArrayList<>();

    for (int i = 0; i < nums.length - 2; i++) {
      if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) { // 跳过可能重复的答案

        int l = i + 1, r = nums.length - 1, sum = 0 - nums[i];
        while (l < r) {
          if (nums[l] + nums[r] == sum) {
            ls.add(Arrays.asList(nums[i], nums[l], nums[r]));
            while (l < r && nums[l] == nums[l + 1]) l++;
            while (l < r && nums[r] == nums[r - 1]) r--;
            l++;
            r--;
          } else if (nums[l] + nums[r] < sum) {
            while (l < r && nums[l] == nums[l + 1]) l++; // 跳过重复值
            l++;
          } else {
            while (l < r && nums[r] == nums[r - 1]) r--;
            r--;
          }
        }
      }
    }
    return ls;
  }

  /**
   * 原答案
   *
   * @param nums
   * @return
   */
  //  public List<List<Integer>> threeSum(int[] nums) {
  //    List<List<Integer>> res = new LinkedList<>();
  //    List<Integer> numTmp = new LinkedList<>();
  //    if (nums.length == 0) {
  //      return res;
  //    }
  //    for (int i : nums) {
  //      numTmp.add(i);
  //    }
  //    numTmp.sort((integer, t1) -> integer >= t1 ? 1 : -1);
  //    int zeroIndex = 0;
  //    for (int i = 0; i < numTmp.size() - 1; i++) {
  //      if (numTmp.get(i) <= 0 && numTmp.get(i + 1) >= 0) {
  //        zeroIndex = i + 1;
  //        break;
  //      }
  //    }
  //
  //    for (int i = 0; i <= zeroIndex; i++) {
  //      if (numTmp.get(i) > 0) {
  //        continue;
  //      }
  //      for (int j = numTmp.size() - 1; j > i + 1; j--) {
  //        if (numTmp.get(j) < 0
  //            | -2 * numTmp.get(i) < numTmp.get(j)
  //            | 2 * numTmp.get(j) < -numTmp.get(i)) {
  //          continue;
  //        }
  //        int k = getIndex(numTmp, 0 - numTmp.get(i) - numTmp.get(j), i, j);
  //        if (k >= 0) {
  //          List<Integer> tmp = new LinkedList<>();
  //          tmp.add(numTmp.get(i));
  //          tmp.add(numTmp.get(j));
  //          tmp.add(numTmp.get(k));
  //          Collections.sort(tmp, (integer, t1) -> integer >= t1 ? 1 : -1);
  //          res.add(tmp);
  //        }
  //      }
  //    }
  //    return getRemoveRepeat(res);
  //  }
  //
  //  public int getIndex(List<Integer> tmp, int val, int start, int end) {
  //    int i = (start + end) % 2 == 0 ? (start + end) / 2 : (start + end - 1) / 2;
  //    int left = start, right = end;
  //    while (tmp.get(i) != val && Math.abs(left - right) >= 2) {
  //      if (tmp.get(i) > val) {
  //        right = i;
  //        i = (right - left) % 2 == 0 ? (right + left) / 2 : (right + left - 1) / 2;
  //      } else if (tmp.get(i) < val) {
  //        left = i;
  //        i = (right - left) % 2 == 0 ? (right + left) / 2 : (right + left - 1) / 2;
  //      }
  //    }
  //    if (Math.abs(left - right) < 2) {
  //      return -1;
  //    }
  //    return i;
  //  }
  //
  //  public List<List<Integer>> getRemoveRepeat(List<List<Integer>> tmp) {
  //    List<List<Integer>> res = new LinkedList<>();
  //    for (int i = 0; i < tmp.size(); i++) {
  //      if (!res.contains(tmp.get(i))) {
  //        res.add(tmp.get(i));
  //      }
  //    }
  //    return res;
  //  }
}
